/**
 * 279. 完全平方数
 * https://leetcode-cn.com/problems/perfect-squares/
 */

/**
 * @param {number} n
 * @return {number}
 */
function numSquares(n) {
  const sqrt = Math.sqrt(n);
  if (Number.isInteger(sqrt)) {
    return 1;
  }
  const dp = new Array(n + 1).fill(0);
  const squares = new Array(Math.floor(sqrt));
  for (let i = 0; i < squares.length; i += 1) {
    squares[i] = (i + 1) * (i + 1);
    dp[squares[i]] = 1;
  }
  for (let i = 2; i <= n; i += 1) {
    if (dp[i] <= 0) {
      let min = Infinity;
      const max = Math.floor(i / 2);
      for (let j = 0; squares[j] <= max; j += 1) {
        const count = dp[i - squares[j]] + 1;
        if (count < min) {
          min = count;
        }
      }
      dp[i] = min;
    }
  }
  return dp[n];
}

console.log(numSquares(12) === 3);
console.log(numSquares(13) === 2);
console.log(numSquares(16) === 1);
